/*
 * region_search.h
 *
 *  Created on: 03.02.2013
 *      Author: Maksim Lazeba
 */

#pragma once

#include <vector>

using std::size_t;

struct rect_t;

struct point_t
{
	std::vector<double> x;
	size_t id;
	int dimensions;

	point_t(std::vector<double> &x, size_t id, int dim) :
			x(x), id(id), dimensions(dim)
	{
	}

	point_t(const point_t &p) :
			x(p.x), id(p.id), dimensions(p.dimensions)
	{
	}

	point_t() :
			id(0), dimensions(0)
	{
	}

	bool smaller(const point_t &b, int dim) const;
	int cmp(double d, int dim) const;
};

struct rect_t
{
	point_t lb;
	point_t rt;

	rect_t(point_t &lb, point_t &rt) :
			lb(lb), rt(rt)
	{
	}

	bool contains(const point_t &p) const;
};

struct region_tree
{
	struct tree_node
	{
		tree_node *left, *right;
		bool leaf;
		double lb, rb;
		int dim;
		tree_node *next_dim_root;
		std::vector<point_t> points; //Sorted by next dimension

		tree_node(tree_node *left, tree_node *right, int dim);
		tree_node(const point_t &point, int dim);
		virtual ~tree_node();

		virtual void add_from_region(const rect_t& rect,
				std::vector<point_t>& ans) const;
		virtual void add_from_region_improved(const rect_t& rect, int lb_cur,
				int ub_cur, std::vector<point_t>& ans) const
		{
		}
	};

	struct improved_tree_node: public tree_node
	{
		struct list_node
		{
			bool end;
			const point_t *point;
			size_t left_lb, left_ub, right_lb, right_ub;
			size_t position;

			list_node(const point_t &p, size_t llb, size_t lub, size_t rlb,
					size_t rub, size_t pos) :
					end(false), point(&p), left_lb(llb), left_ub(lub), right_lb(
							rlb), right_ub(rub), position(pos)
			{
			}

			list_node(const point_t &p) :
					end(false), point(&p), left_lb(0), left_ub(0), right_lb(0), right_ub(
							0), position(0)
			{
			}

			list_node(size_t left_end, size_t right_end, size_t pos) :
					end(true), point(0), left_lb(left_end), left_ub(
							left_end), right_lb(right_end), right_ub(right_end), position(
							pos)
			{
			}

			bool operator<(const list_node &b) const;
			bool operator<(const point_t &b) const;
		};
		std::vector<list_node> list;

		improved_tree_node(tree_node *left, tree_node *right, int dim);
		improved_tree_node(const point_t &point, int dim);
		~improved_tree_node();
		void add_from_region(const rect_t &rect,
				std::vector<point_t>& ans) const;
	private:
		void add_from_region_improved(const rect_t& rect, int lb_cur,
				int ub_cur, std::vector<point_t>& ans) const;
	};

	tree_node *root;
	std::vector<point_t> points; // Used when there is just 1 dimension
	int dimensions;

	region_tree(std::vector<point_t> &points, int d);
	~region_tree();
	std::vector<point_t> get_points_in_rect(const rect_t &rect) const;
};

